//https://leetcode.cn/problems/copy-list-with-random-pointer/
//随机链表的复制

class Solution {
public:
    Node* copyRandomList(Node* head) {
        map<Node*, Node*> m;
        m[nullptr] = nullptr;
        Node* cur = head;
        while(cur)
        {
            m[cur] = new Node(cur->val);
            cur = cur->next;
        }

        cur = head;
        while(cur)
        {
            m[cur]->next = m[cur->next];
            m[cur]->random = m[cur->random];
            cur = cur->next;
        }
        return m[head];
    }
};